//1.dfs最好理解
class Solution {
public:
    void act(int i, int j, vector<vector<char>>& grid, int m, int n) {
        if(i<0 || i>=m || j<0 || j >= n || grid[i][j]=='0') 
            return;
        grid[i][j]='0';
        act(i-1, j, grid, m, n);
        act(i, j+1, grid, m, n);
        act(i+1, j, grid, m, n);
        act(i, j-1, grid, m, n);
        
    }

    int numIslands(vector<vector<char>>& grid) {
        int count=0;
        int m = grid.size();
        int n = grid[0].size();
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n;++j) {
                if(grid[i][j]=='0')
                    continue;            
                count++;
                act(i, j, grid, m, n);
            }
        }
        return count;
    }
};
//1.1 act函数优化，进入递归前判断
void act(int i, int j, vector<vector<char>>& grid, int m, int n) {      
    grid[i][j]='0';
    if(i - 1 >= 0 && grid[i-1][j]=='1')  act(i-1, j, grid, m, n);
    if(j + 1 < n && grid[i][j+1]=='1')  act(i, j+1, grid, m, n);
    if(i + 1 < m && grid[i+1][j]=='1')  act(i+1, j, grid, m, n);
    if(j - 1 >= 0 && grid[i][j-1]=='1')  act(i, j-1, grid, m, n); 
}

   

//2.bfs-----队列
class Solution {
public:
    int numIslands(std::vector<std::vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) {
            return 0;
        }

        int m = grid.size();
        int n = grid[0].size();
        int count = 0;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // 找到一个新岛屿的起点
                if (grid[i][j] == '1') {
                    count++;
                    // 开始 BFS 淹没整个岛屿
                    queue<pair<int, int>> q;
                    q.push({i, j});
                    // 标记起点已被访问，防止重复入队
                    grid[i][j] = '0'; 

                    while (!q.empty()) {
                        pair<int, int> curr = q.front();
                        q.pop();

                        int r = curr.first;
                        int c = curr.second;

                        // 定义四个方向: 上, 下, 左, 右
                        int dr[] = {-1, 1, 0, 0};
                        int dc[] = {0, 0, -1, 1};

                        // 探索四个方向的邻居
                        for (int k = 0; k < 4; ++k) {
                            int new_r = r + dr[k];
                            int new_c = c + dc[k];

                            // 检查邻居是否有效 (在边界内且是陆地 '1')
                            if (new_r >= 0 && new_r < m && new_c >= 0 && new_c < n && grid[new_r][new_c] == '1') {
                                q.push({new_r, new_c});
                                // 标记新发现的陆地已被访问
                                grid[new_r][new_c] = '0';
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
};



